`
https://leetcode.cn/problems/longest-palindromic-subsequence/
`

/**
 * @param {string} s
 * @return {number}
 */
var longestPalindromeSubseq = function (s) {
  const n = s.length

  // dp[i][j] 表示 s[i...j] 的最长回文子序列长度
  const dp = Array.from({ length: n }, () => new Array(n).fill(0))

  // i === j 时，只有一个字符，必是回文，即 dp 数组对角线上的都是 1
  for (let i = 0; i < n; i++) {
    dp[i][i] = 1
  }

  // 最终的结果是 dp[0][n-1] 这里选择反着遍历
  for (let i = n - 1; i >= 0; i--) {
    for (let j = i + 1; j < n; j++) {
      // 说明两端新加进来的字符相同，说明都在 lps 内
      if (s[i] === s[j]) {
        dp[i][j] = dp[i + 1][j - 1] + 2
      } else {
        // 不相同，则取 s[i+1...j] 和 s[i...j-1] 的最大值
        dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1])
      }
    }
  }

  return dp[0][n - 1]
};

// test
console.log(longestPalindromeSubseq("bbbab")) // 4
console.log(longestPalindromeSubseq("cbbd")) // 2